1. Field of the Invention
The present invention relates generally to computer system memories. Specifically, the present invention relates to a memory manager implemented on a hand-held device.
2. Related Art
Generally speaking, in one implementation of a memory architecture on a hand-held device (commonly referred to as personal digital assistants or PDAs), the memory is divided into one or more “heaps.” A heap is a contiguous area of memory that includes multiple “chunks.” A chunk is an area of contiguous memory within a heap. When applications work with memory, they usually work with chunks of memory. A memory manager executed by the device's operating system manages each heap independently, allocating chunks to requesting applications, keeping track of the locations of chunks, and rearranging chunks as necessary to defragment heaps and merge free space.
In one prior art implementation, a chunk is aligned on word boundaries; that is, the starting point of a chunk is aligned with the starting point of a region of memory that is two bytes in length. In another prior art implementation, a chunk is aligned with a region of memory that is four bytes in length. Note that a chunk may include multiples of such regions.
Each chunk in memory is located using a reference that may be known as a local identifier (local ID). When the memory manager allocates a chunk, it generates and stores a pointer to the chunk. The reference or local ID is the offset of the pointer from the base address of the memory module on which the chunks reside. The memory module may be a physical component of the computer system, or it may be a convenient logical construct of the computer system's memory.
Associated with each chunk is a chunk header. A chunk header generally has the following structure:
typedef struct{UInt32size:24;// actual size of chunkUInt32sizeAdj:4;// size adjustmentUInt32unused3:1;// unusedUInt32unused2:1;// unusedUInt32moved:1;// used by MemHeapScrambleUInt32free:1;// set if free chunkInt32hOffset:24;// signed MemHandle offset/2// used in free chunks to point to// next free chunkUInt32owner:4;// owner IDUInt32lockCount:4;// lock count} MemChunkHeaderType;
Some of the elements listed above are particularly relevant to this discussion and so are further described below; the remaining elements are known in the art and thus are not described further.
The “size” element (or field) is 24 bits in length and describes the size of the chunk associated with the header. This size is larger than the chunk size requested by an application because it includes the size of the header as well as the size of the chunk itself.
The “sizeAdj” field is four bits in length and is used to calculate the requested size of the chunk given the actual size provided by the size field.
The hOffset field is 24 bits in length. For a free (unused) chunk, the value of hOffset provides the distance to the next free chunk. For an allocated (used) chunk, the value of hOffset provides the distance between the pointer and the base address, divided by the binary equivalent of two. Because a chunk is aligned at least to a word boundary as mentioned above, the least significant bit of the actual offset is always zero. By dividing the actual offset value by a binary two, the least significant bit is in effect truncated.
One of the 24 bits in the hOffset field is a sign bit, because the offset can be a negative value (if the base address is higher than the actual address of the chunk, for example). To determine the actual offset from the value provided by hOffset, the bits in the hOffset field are multiplied by a binary two, yielding a 24-bit address ending with a bit value of zero, plus the sign bit. The sign bit identifies which direction to move within the heap. In this manner, 23 bits (24 bits minus the sign bit) can be used to address a memory range of up to 16 megabytes (MB), moving in either direction within the memory (±16 MB).
While 16 MB of memory may be adequate for many applications, a desire to increase memory capacity remains. The increase in the number and complexity of software applications is one factor in the drive for larger memories. Other motivating factors include consumer preferences and competitive pressures.
Hardware improvements allow memories with larger capacities to be used in smaller form factor devices such as hand-held computer systems. Hardware improvements include the use of Advanced RISC (reduced instruction set computer) Microprocessors (ARMs) as well as the development of higher density memory devices. Memory capacities of up to 128 MB can be introduced into hand-held computer systems. However, the prior art is problematic because only 16 MB of memory can be addressed.
Accordingly, an addressing system and/or method that can support larger memories, in particular memories up to 128 MB in size, is desirable. One issue to consider is the impact on the operating system(s) currently in use; it is desirable to minimize the impact on existing software tools. Another issue to consider is compatibility with applications in use, particularly third-party applications; it is desirable to maintain compatibility with those applications. The present invention provides a novel solution that can satisfy these desires.